1. Field of the Invention
This invention relates to systems and methods that automatically schedules and dispatches orders for the fabrication and testing of products to a manufacturing line. More particularly, this invention relates to systems and methods for simulating and predicting the operation of a manufacturing line that provides an efficient schedule for the fabrication and testing of the products.
2. Description of Related Art
Automated manufacturing systems have improved the productivity of manufacturing firms. The tool elements of a manufacturing system must be organized to produce the total product set that is marketed by the firm. To insure that the total elements are used efficiently, a manufacturing execution system (MES) includes a facility that controls the scheduling and dispatching of production lots to the manufacturing line. Upon scheduling the production lots, the tool elements are configured for production and appropriate testing systems are installed to verify of the quality and functioning of the product being fabricated. Dispatching the production lots may be affected by a number of factors such as types of equipment needed for the fabrication and testing, maintenance of the equipment, arrival of high priority orders (hot lot or super hot lot) that are not anticipated within the scheduling of the production lots, delays in requests for production, etc.
Traditionally the method executed by MES scheduling and dispatch facility, as shown in FIG. 1, receives forecasting and scheduling information from the marketing and sales database. This forecasting and scheduling information includes the product mix forecast 5, the product volume forecast 10, the predicted sales schedule 15, the sales confidence 20, the actual sales order descriptions 25, and the produced delivery schedule 30. The product mix forecast 5 and the actual sales order descriptions 25 provide a listing of the types of products to be fabricated. The listing of products is used to acquire the product process description 35 detailing the types of manufacturing equipment capabilities and capacities needed to fabricate the products as predicted and ordered. Once the required equipment is identified, the process equipment inventory 40 is retrieved. From the above information, a process equipment requirement and allocation plan is created (Box 45). The process equipment requirements and allocation plan 52, the allocated process equipment capability 50, and the allocated process equipment capacity 55 are used to generate (Box 60) a process equipment schedule. The process equipment schedule 62, the status of the lots of product at each stage of fabrication 65, and an equipment dispatch algorithm 70 are used for dispatching (Box 75) the processing equipment for the fabrication and testing of the product. Upon dispatching (Box 75) and configuring the equipment, the product such as semiconductor wafers is processed (Box 80) to complete the fabrication and testing.
“Modeling and Analyzing Workflow Using a Petri-Net Based Approach”, van der Aalst et al., Proceedings 2nd Workshop on Computer-Supported Cooperative Work, Petri Nets and Related Formalisms, pp. 31-50, 1994 describes high-level Petri nets used to model systems in a variety of application domains, ranging from protocols to logistics. The high-level Petri nets are used to model (1) the workflow in an office environment and (2) the workflow management system to support the control of office work.
“Generic Workflow Models: How To Handle Dynamic Change and Capture Management Information?”, van der Aalst, “Proceedings—1999 IFCIS International Conference on Cooperative Information Systems, 1999, Edinburgh, UK, pp: 115-126, describes two problems related to adaptive workflow: (1) providing management information at the right aggregation level, and (2) supporting dynamic change, i.e., migrating cases from an old to a new workflow. These two problems are tackled by using generic process models employing Petri nets to illustrate the main concepts.
“Modeling, Scheduling, And Prediction in Wafer Fabrication Systems Using Queuing Petri Net and Genetic Algorithm”, Wen et al. Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation, 2001 , vol.4, pp: 3559-3564 provides a modeling tool called queuing-Petri net (Q-PN) which combines the characteristics of queuing theory and Petri nets. It can be used to model various details of the manufacturing systems as well as to efficiently evaluate its performance. A general Q-PN model is presented to simulate the semiconductor manufacturing system. Based on this model, a genetic algorithm (GA) based scheduler and an analysis-based predictor is described.
“Petri Net Based Modeling of Job-Shop Resource Allocation in Generic Prototyping Approach”, Neagu, IEEE International Conference on Systems, Man, and Cybernetics, 1998, vol.1, pp: 96-100, presents the decision control Petri nets (DCPN) structure for behavior modeling in discrete event systems. In the case of components with inherit decision-making capabilities, this structure proposes the decision transition mechanism to activate suitable decision support resources. A multi-agent simulator is envisaged to generate a scheduling solution based on job-shop representation as a network of interconnected resource allocation center.
“Deadlock-Free Scheduling of Flexible Manufacturing Systems Based on Heuristic Search and Petri Net Structures”, Jeng et al. IEEE International Conference on Systems, Man, and Cybernetics, 1998, vol.1, pp: 26-31 proposes a modified best-first algorithm and applies it to a flexible manufacturing system with assembly. A heuristic function based on the Petri net structure and dynamics is presented. The heuristic function consists of two parts. The first part estimates the total remaining operation time for all jobs considering system dynamics. The second part approximates the maximal total remaining operation time for each job.
“Modeling and Performance Analysis of Workflow Management Systems Using Timed Hierarchical Colored Petri Nets”, Salimifard, et al., Proceedings of ICEIS 2002, Vol. 2, pp 843-846, 2002 illustrates a modeling methodology for workflow management systems based on colored Petri nets. Using an integration method, processes and resources are modeled at the same abstraction level. A process is decomposed into task structures, human resources are considered at role level. Activity based costing is combined with classical temporal analysis of workflow.
U.S. Pat. No. 5,826,040 (Fargher, et al.) describes a method for planning a production schedule within a factory. A capacity model is created by determining contiguous time intervals, partitioning the factory into resource groups, and determining a processing capacity for each of the resource groups for each of the time intervals. Each job to be planned is divided into processing segments that is represented by a corresponding fuzzy set. The fuzzy set representations are inserted and removed within the capacity model until the job is planned. A completion date and a confidence level can be predicted for each of the jobs. In addition, the jobs requirements may be released to the factory and devices fabricated accordingly.
U.S. Pat. No. 6,185,469 (Lewis, et al.) provides methods and apparatus for testing flexible manufacturing systems. Matrix logic equations are used to process data on the event-states of associated Petri nets and to provide rules for the assignment of resources and work pieces to future event-states that correspond with to yet to be performed jobs. The devices start and stop individual resources in response to logic signals. Sensor feedback is obtained for the distribution of work pieces and available resources in the manufacturing system.
U.S. Pat. No. 6,263,303 (Yu, et al.) describes a simulator particularly suited for simulating the hardware/software behavior of embedded systems. The architecture of the simulator permits the hardware and software systems to be modeled as modules with well characterized behaviors. A concise module definition syntax employing Petri-net like transition objects is used to describe module behaviors. A translator operates upon the module to abstract operations of module behaviors at a level which does not require cycle-based, direct interaction of each module with the underlying simulation engine.